\chapter{背景知识和相关工作}
为了理解YAFFS2文件系统的设计理念和具体的实现细节，我们需要首先理解闪存芯片的技术特性。本章的2.1
节将提供为了理解YAFFS2文件系统在闪存上的存储结构所必要的对闪存芯片的抽象。第2.2节中将介绍YAFFS2
文件系统的设计理念以及对文件恢复工作有着重大意义的一些实现细节。第2.3节将介绍在文件系统取证分析领域
内的相关工作。
\section{闪存}
闪存(Flash memory)是一种使用了浮栅晶体管\cite{reberto}作为位存储单元的电可擦除只读存储器(EEPROM)。相比于
磁盘更佳的抗震性能、高存储密度以及低廉的价格，使它成为最常用的移动设备存储媒介。

作为一种只读存储器，闪存芯片并不适合进行多次数的擦除，因此生产厂商对擦除操作做出了限制。“块（Block)”
是最小的擦写单元。如果要改变芯片中某一位的值，就需要擦除整个这一位所在的块，然后写入更改后的内容。
还要指出的是，每个块都有有限的擦除寿命，当擦除次数超过这个限度后，该块就有可能损坏。这是为闪存专门设计
文件系统的最重要的原因，文件系统需要尽可能地使每个块都被均匀地损耗，以最大限度地延长闪存的寿命。

\subsection{闪存的主要类型}
根据物理实现方式不同，闪存分为NOR和NAND两种类型。具体的物理实现细节不是本文讨论的重点，在这里
我们仅指出两者的主要表现特性的不同：
\begin{center}
\captionof{table}{Micron MT29F2G08A NAND闪存和Micron TE28F128J3 NOR闪存的比较\cite{micron}}
\begin{tabular}{|c|c|c|}
\hline
特性 & NOR & NAND \\
\hline
\hline
最小寻址单元 & 1 byte & 1 page (2048B + 64B OOB) \\
\hline
随机读取时间 & 0.075$\mu$ s & 25$\mu$ s(首字节）, 0.025$\mu$ s（该页其余的字节）\\
\hline
随机写入速度 & 约220$\mu$ s/page & 128$\mu$ s/ 128bytes \\
\hline 
最小擦除单元 & 128 KB & 128KB \\
\hline
每单元擦除速度 & 500$\mu$ s & 1 s \\
\hline
\end{tabular}
\end{center}

可以看出，NAND闪存拥有较快的读写速度，适合大量数据的读写。而NOR闪存拥有更小的读写单位，适合用于
存储机器指令。另外，对于同样的存储控件，NAND闪存可以用更少的引脚来访问，因此NAND能保证芯片的封装
面积较小的同时拥有更大的容量。所以移动设备都选择NAND闪存作为自己的外存，而NOR一般仅用作存储一些
小的程序（如用于BIOS芯片）。

虽然YAFFS2也可以使用在NOR介质上，但它对闪存的接口抽象与NAND的物理抽象相同，并且绝大多数情况
下使用在NAND闪存芯片上，本文所做的测试以及实验都是基于NAND闪存芯片的。因此如没有别指出，本文
以后提及的“闪存”均指NAND闪存。

\subsection{NAND闪存的逻辑视图}
NAND闪存的最小读写单位是页(pages)；最小擦除单位是块(block)~\cite{micron}。通常，一块由1到若干页组成。需要
指出的是，写入和擦除在原理上分别对应晶体管状态的复位和置位。因此写入操作只能作用与一个所有位都
为1的页，而擦除操作则是把一块中的所有位都置位。

\begin{center}
\includegraphics[scale=0.6]{img/nand.png}
\captionof{figure}{NAND闪存的逻辑视图}
\end{center}

YAFFS2也使用这样的逻辑视图来看待NAND闪存，但是术语略有不同：YAFFS2使用"chunk"表示NAND闪存
的"pages"的概念（可能1个chunk包含多个pages，但是chunk是YAFFS2使用的最小的读写单位），
因此下文中这两个术语将有同一含义。

\subsection{NAND闪存的带外(OOB)区域}
为了标记坏块并且存储校验信息，NAND闪存的每一页都有一小块额外的，称之为带外区域（Out-of-band area）
的存储空间。如果OOB区域中空闲的空间足够大，那么YAFFS2将使用它存储关于这一页的元信息（见下一小节）。但
由于校验码是硬件生成的，并且根据硬件厂商的设置存储在OOB区域的不同位置，因此在处理一个NAND镜像
时，需要首先获得该镜像来源设备的OOB布局。

\section{YAFFS2}
\subsection{简介}
"YAFFS"是Yet Another Flash File System的缩写。它是一个兼容POSIX接口的文件系统，可以运行在
任何POSIX兼容的操作系统下。YAFFS的设计目标是在NAND闪存的技术特性限制下，
利用NAND的有点来最大化性能的文件系统\cite{manning02}。YAFFS的特点有\cite{yaffshome}：
\begin{itemize}
\item 可运行在NAND或NOR闪存上。
\item 提供均匀擦除特性(Wear Levelling)。
\item 良好的纠错功能。
\item 更少的RAM使用量。
\end{itemize}
YAFFS2的部分代码继承自YAFFS1，但是重新设计了删除操作，使这个文件系统成为完全日志结构，即从不改写已经
写入的数据。由于YAFFS1不支持512字节以上的页面大小，在当前NAND闪存页面大小多为4096字节的情况下，
几乎所有移动设备上运行的YAFFS都是YAFFS2。

在YAFFS2、JFFS2和UBIFS的横向评测中，YAFFS2表现出了最佳的写性能以及在小分区（小于200MB）条件下最佳的
读性能\cite{opdenacker}。

\subsection{YAFFS2的工作原理}
本节将介绍YAFFS2是如何将文件数据存储到闪存上、存储并管理文件元数据以及如何在引导时扫描闪存以获得
闪存上所有文件的信息的。由于YAFFS2的运行时内存结构对文件恢复工作没有意义，在这里不做过于详尽的介绍。

\subsubsection{对象(object)}
YAFFS2将文件系统中存储的所有个体都视作对象\cite{manning07}，这些个体包括：
\begin{itemize}
\item 普通文件
\item 文件目录
\item 硬链接
\item 符号链接
\item 特殊对象（如管道、设备等）
\end{itemize}

\subsubsection{节(chunk)}
如前所述，YAFFS2的最小读写单位是chunk，因此每一个对象都可以看作是若干chunk的有序集合。组成文件的
chunks分为两类：header chunk与data chunk：header chunk用于存储文件的元信息；data header
用于存储文件的内容。对文件恢复有意义的元信息包括：
\begin{itemize}
\item 文件名
\item 文件大小
\item 文件类型
\item 父对象（指向父目录）
\item 时间戳
\item 权限
\item 所有者
\end{itemize}
每一个对象都有1个有效的header chunk和零到多个有效的data chunks。

每一个chunk也包含有各自的元信息，YAFFS需要它们来鉴别一个chunk的所属文件等重要信息。
它们可能储存在闪存页面的OOB区域内，也可能同数据一起放在数据区域内。
这些元信息包括：
\begin{itemize}
\item chunkID: 该chunk在对象中的逻辑位置，该值为0则意味着该chunk是一个object header。
\item objectID: 对象的唯一标识。
\item blockState: 该chunk所在的block的状态。它指出了这个block是否为空、是否有用以及是否已经损坏。
\item blockSequence: 严格单调递增的块顺序号，该号码代表了块的分配顺序。
\item nBytes: 该chunk中包含有效数据的大小。
\end{itemize}

\subsubsection{块(block)}
block是YAFFS2的最小擦除单位，1个block可以包含1到多个chunks。YAFFS2的block概念同NAND的block概念
相同。

\subsubsection{日志结构}
YAFFS2是一个全日志结构的文件系统，这意味着\cite{manning07}：
\begin{itemize}
	\item 零覆盖：从不改写已经写入到NAND的chunk；零覆盖的意义在于适应当前NAND硬件对覆写的低容忍度。
	\item 块内节顺序写：在同一个block内，chunk的写入顺序与其逻辑地址顺序相同；多数NAND硬件要求块内顺序写的特性。
\end{itemize}

以上两条性质使得YAFFS2像记录日志一样按照时间顺序完整地记录了一个对象的所有修改历史。根据chunk元信息中的blockSequence以及chunk
在块内的偏移，我们可以比较两个chunk写入的先后顺序，进而得知它们的新旧。而objectID和chunkID则能确定该chunk所属的对象以及是对象的哪一部分。
对于所有拥有同样的(objectID, chunkID)的chunk，最新的一个就是该对象该部分的最新版本。下面使用一个示例来介绍存储过程的细节。简单起见，我们
假设一个block仅包含4个chunks，并且文件系统中只有1个文件。

\begin{center}

\begin{tabular}{|c|c|c|}
\hline
blockSequence:chunkNum & chunkID & Content \\
\hline
\hline
0:0 & 1:0 & Header 1 (size = 0) \\
\hline
0:1 & 1:1 & Data Chunk 1 \\
\hline
0:2 & 1:2 & Data Chunk 2 \\
\hline
\multicolumn{3}{c}{...} \\

\hline
3:0 & 1:8 & Data Chunk 8 \\
\hline
3:1 & 1:9 & Data Chunk 9 \\
\hline
3:2 & 1:0 & Header 2 (size = 9) \\
\hline
3:3 & 1:0 & Header 3 (size = 3)* \\
\hline
\hline
4:0 & 1:8 & Data Chunk 8 \\
\hline
4:1 & 1:0 & Header 4 (size = 8) \\
\hline
4:2 & 1:0 & Header 5 (deleted) \\
\hline
4:3 & \multicolumn{2}{|c|}{empty} \\
\hline
\end{tabular}
\captionof{figure}{示例：一个文件在NAND上的YAFFS2日志结构}
\captionof*{figure}{size代表文件的大小，以chunk数计;由于仅有1个文件，因此objectID均为1}
\end{center}
上面的示例中，每行代表一个chunk，每4行组成一个block；行按照(blockSequence，chunkNum)进行排序。
由于blockSequence:chunkNum对每个chunk是唯一的，因此在下面的介绍中用这种方式来表示一个chunk。
因为blockSequence是block按时间分配的顺序号，并且在一个block内只能顺序写入，因此表格中的行从上自下
按照写入时间的先后顺序排列。

这个文件经历了如下的操作（用POSIX文件操作原语表示\cite{POSIXFileOP}）：
\begin{enumerate}
\item open（写入0:0，即一个头节，其中文件大小字段为0）
\item write（写入9个chunks的数据；写入0:1 - 3:1）
\item close（写入3:2，即一个头节，其中文件大小字段为9）
\item truncate （将文件截短至大小3；写入3:3）
\item write（在offset=8处写入大小为1的内容；写入4:1）
\item close (写入4:2，即一个头节，其中文件大小字段为8)
\item delete （写入4:3，即一个头节，其中文件的父目录为"lost+found"）
\end{enumerate}

YAFFS2可以通过如下方式获知文件当前的状态以及它由哪些chunks组成：
\begin{enumerate}
\item 将该文件的所有chunks按写入时间排序。
\item 找到该文件写入时间最晚的chunk。不考虑意外掉电等情形时，该chunk应当是一个header。这个
header包含有最新的文件元信息。
\item 按照写入时间的倒序依次检查每个chunk，若该chunk的chunkID第一次出现，那么可以确定该chunk包
含有这一部分的最新内容。若不是第一次出现，则抛弃（并标记为闲置）该chunk。
\item 如果收集到的chunk的总大小小于文件大小，则文件缺少的位置的所有字节都为0。
\end{enumerate}

\subsubsection{垃圾回收}
至此，YAFFS2已经能够进行正常的文件读写，但是作为一个面向NAND的文件系统，仍存在以下问题：
\begin{enumerate}
	\item 只写入不擦除，最终NAND会被历史数据充满以至于无法再进行写入，而逻辑上来看该NAND并没有满。
	\item 如果有一些块在被写入后一直是有效的，那么这些块就永远不会被更改，以至于增加了其他块的使用次数，使得
	块的寿命不均等。
	\item 有一些块在写入时发生了错误，这通常表示它们即将变成坏块，需要及时将这些块中的数据复制到正常的块中。
\end{enumerate}

YAFFS2的垃圾回收机制能够解决这些问题。垃圾回收(garbage collection)的功能是释放过期的数据节所占用的空间，
由于擦除操作的最小单位是块，所以垃圾回收可能涉及到将块内有效的节复制到另一个新分配的块中，然后再执行擦除。

YAFFS2采用了最老脏块回收(oldest dirty garbage collection)策略。同时有被动回收和主动回收两种方式。
被动回收方式主要为了解决问题2和3：回收器会优先选择最老的并且发生过写入/读取校验错的块；如果不存在这样的
块，就选择最老的，并且块中有效节少于一个常数的块（默认为4）；如果依然不存在这样的块，那么就不进行回收。在
被动回收执行多次仍没有回收任何块的情况下，被动回收会强制选择最老的脏满块进行回收。
被动回收会由一个后台线程以固定的时间间隔触发，同时，当处于脏块中的空闲节数量和空闲节总数的比例超过一个阈值时，即
无法被利用的自由空间超过一定比例时，每次向NAND写入时也会启动被动回收。主动回收的主要目的
是收复被无效数据占用的空间，它一定会选出一块来进行回收。主动回收仅在空间不足时触发。

由于被动回收对最老的脏块的回收是不可避免的，在不产生新的节的前提下，所有无效节最终都将被回收掉。文件恢复实际上是
与垃圾回收进行赛跑：NAND设备挂载的时间越长，能恢复到的数据就越少。

论文\cite{Zimmermann}中对垃圾回收对YAFFS2上文件恢复的效果的影响做了较为详细的分析和测试：在NAND上有足够的空间，
即NAND上有着较为充足的可用节的情况下，垃圾回收就只会采用被动方式，并以很长的时间间隔（实际为24秒）来“刷新”最老的块。
对于存储了较多的数据的大容量NAND，在没有新数据产生的情况下将所有的无效节都清除可能需要若干小时至若干天时间。

\subsubsection{缩减标记头（shrink header)}
上一小节已经介绍了YAFFS2的大部分存储细节，但是若按照上述方法对前例进行扫描，会引起如下问题：
3:3的truncate操作执行后开始，从2:1 -- 3:2的所有chunk都被标记为了闲置。在4:2的header写入后，
3:3也被标为闲置，这样，整个block 3中的所有chunk都已经是闲置chunk。如果此时仅block 3被垃圾回收清零，
那么在执行前述的扫描时，会data chunk 3 -- data chunk 7中填充0:3 -- 2:3的内容。而实际上，在3:3的truncate
操作后，这部分内容应当已经不存在，在4:1写入后，文件中应当存在一个“洞”，这个“洞”中的内容应当是全0。正误两种情况
对比如下图：
\begin{center}

\begin{minipage}{0.4\textwidth}
\begin{tabular}{|c|c|}
\hline
Chunk \# & Content \\
\hline
1 & Data Chunk 1 \\
\hline
2 & Data Chunk 2 \\
\hline
3 & Data Chunk 3 \\
\hline
4 & Data Chunk 4 \\
\hline
5 & Data Chunk 5 \\
\hline
6 & Data Chunk 6 \\
\hline
7 & Data Chunk 7 \\
\hline
8 & Data Chunk 8 (4:1)  \\ 
\hline
\end{tabular}
\end{minipage}
\hspace{1em}
\begin{minipage}{0.4\textwidth}
\begin{tabular}{|c|c|}
\hline
Chunk \# & Content \\
\hline
1 & Data Chunk 1 \\
\hline
2 & Data Chunk 2 \\
\hline
3 & Data Chunk 3 \\
\hline
4 & 0 (truncated whole)\\
\hline
5 & 0 (truncated whole)\\
\hline
6 & 0 (truncated whole)\\
\hline
7 & 0 (truncated whole)\\
\hline
8 & Data Chunk 8 (4:1) \\ 
\hline
\end{tabular}

\end{minipage}
\captionof{figure}{Shrink header用途示例。左：若Shrink header被忽略，则文件中的“洞”将表示错误；右：正确情形。}
\end{center}
问题的根源在于标示了“洞”的header (3:3)被垃圾回收了。因此header拥有一个特殊的属性：shrinkHeader。若该属性为真，
那么垃圾回收会将这个chunk视为有效，并且不优先回收该chunk所在的block。由于垃圾回收机制对缩减头的特殊处理，使得包含有
缩减头节的块非常不易被回收。因此truncate操作将潜在地提高文件恢复的效果。

\section{文件系统取证与分析的相关工作}
目前，文件系统取证与分析的主要工作成果都是针对流行的磁盘文件系统。书\cite{Brian05}对这些工作
成果进行了总结。这一领域最初的工作是针对已经发表的文件系统的设计结构，来考虑如何恢复该文件系统
中已经标记为删除但没有从磁盘上抹去的数据，如针对Ext2文件系统的分析工具\cite{Dubeau04}以及针对
苹果UFS+的分析恢复工具\cite{Aaron08}。

与此同时，另一些工作如对未完全恢复的结构化文件进行有用信息提取进行了研究，例如\cite{Sangjun11}
对SQLite数据库文件中已经删除的行进行分析并恢复。

对于移动设备，这一领域目前的工作有：1)针对结构化但未知结构的数据，如非智能手机通讯录、通话记录和短信记录
进行分析恢复的工作，如\cite{Robert11}中的DEC0DE系统能够对NOKIA手机存储的结构化信息进行恢复。2)分析
Android设备常见的文件系统的结构，如\cite{Zimmermann}对YAFFS2文件系统对于取证分析有影响的特性进行
了分析和测试，提出了恢复与反恢复的一些可能的策略。\cite{Baiyi}中的工作对YAFFS1文件系统进行了分析和恢复，
并给出了一个不完整的实现。3）针对分析恢复工具，考虑反恢复策略，如\cite{Pietro11}。

本文提出的YAFFS2分析恢复工具部分基于\cite{Baiyi}和\cite{Zimmermann}的工作。


